User blog:Ikosarakt1/Fast-growing hierarchy
Basic rules First, we have three main rules for FGH. I shall use S for successor ordinal, L for limit ordinal, T for transfinite ordinal and n for n-th term of the fundamental sequence. \alpha can stand for either number or transfinite ordinal. Rule M1. Condition: \alpha = 0 f_0(n) = n+1 Rule M2. Condition: \alpha = S f_{\alpha+1}(n) = f^n_\alpha(n) Rule M3. Condition: \alpha = L f_{\alpha}(n) = f_{\alphan}(n) It order to get to \epsilon_0 and for further purposes, I define the ordinal arithmetic (closed under addition, multiplication and exponentiation): Rule A1. Condition: \alpha=T 1+\alpha = \alpha Rule A2. Condition: \(\beta\) is higher order epsilon ordinal or \(\alpha\) is not an epsilon ordinal, while \(\beta\) is. \alpha^\beta = \beta Rule A3. Condition: \beta=S \alpha*(n+1) = \alpha*n+\alpha \alpha^{\beta+1} = \alpha^\beta*\alpha Also, some basic fundamental sequence rules that will be useful. Rule B1. Condition: \alpha = \omega . \omegan = n Rule B2. Condition: \beta_1 \geq \beta_2 \geq\cdots\geq\beta_m,\alpha_1 \geq \alpha_2 \geq\cdots\geq\alpha_m,m\geq 2 , \(\alpha_p\) isn't a sum, product or exponential of some other ordinals. ({\alpha_1}^{\beta_1}+{\alpha_2}^{\beta_2}+\cdots+{\alpha_m}^{\beta_m})n = {\alpha_1}^{\beta_1}+{\alpha_2}^{\beta_2}+\cdots+{\alpha_m}^{\beta_m}n After applying this rule, repeat rules A1-A3. Rule B3. Condition: \beta is L and \alpha^\beta \neq \beta \alpha^\betan = \alpha^{\betan} When we set \alpha = \beta = \omega , we can easily define fundamental sequences for all ordinals up to \epsilon_0 . Below are some examples: \omega*2n = (\omega+\omega)n = \omega+\omegan = \omega+n \omega*(m+1)n = (\omega*m+\omega)n = \omega*m+\omegan = \omega*m+n \omega^2n = (\omega*\omega)n = \omega*\omegan = \omega*n \omega^{m+1}n = (\omega^m*\omega)n = \omega^m*\omegan = \omega^m*n (\omega^\omega)n = \omega^{\omegan} = \omega^n (\omega^{\alpha+1})n = (\omega^\alpha*\omega)n = \omega^\alpha*\omegan = \omega^\alpha*n In \omega^\omega , we can replace upper \omega to the expressions above it, and we can get fundamental sequences too. Iterating this process again and again, we can define any tree ordinal composed with \omega s and finite numbers. Thus, the notation I defined just now has limit ordinal \epsilon_0 . Compare it with other notations like tetrational arrays in BEAN and Bird's nested array notation. Binary phi function In order to get further, I must use \phi(\alpha,\beta) function. \alpha and \beta can be S, L, 0 or 1, so we get at most 4^2 = 16 rules. Some of them can be removed since for \alpha = 0 : \beta can be any countable ordinal and when \beta = L : \alpha can be any countable ordinal expect 0. Also, 1 is particular case only for \alpha , for beta 1 is S. So, the rules: Rule PB1. Condition: \alpha=0 \phi(0,\beta)n = \omega^{\beta}n Repeat the block of rules A1-A3. Rule PB2. Condition: \alpha=1, \beta=S \phi(1,\beta+1)1 = \phi(1,\beta) \phi(1,\beta+1)n = \phi(1,\beta)^{\phi(1,\beta+1)n-1} Rule PB3. Condition: \alpha=L, \beta=0 \phi(\alpha,0)n = \phi(\alphan,0) Rule PB4. Condition: \alpha=L, \beta=S \phi(\alpha,\beta+1)n = \phi(\alphan,\phi(\alpha,\beta)+1) Rule PB5. Condition: \alpha=S, \beta=0 \phi(\alpha+1,0)1 = \phi(\alpha,0) \phi(\alpha+1,0)n = \phi(\alpha,\phi(\alpha+1,0)n-1) Rule PB6. Condition: \alpha=S,\alpha>1, \beta=S \phi(\alpha+1,\beta+1)1 = \phi(\alpha+1,\beta)+1 \phi(\alpha+1,\beta+1)n = \phi(\alpha,\phi(\alpha+1,\beta+1)n-1) Rule PB7. Condition: \beta=L \phi(\alpha,\beta)n = \phi(\alpha,\betan) Note: the number of rules can be reduced by 1, if we adopt Rule P5 for \alpha = 1 and remove Rule P2. In that case, we get \epsilon_1 = lim(\epsilon_0+1,\omega^{\epsilon_0+1},\omega^{\omega^{\epsilon_0+1}},\cdots) instead of \epsilon_1 = lim(\epsilon_0,\epsilon_0^{\epsilon_0},\epsilon_0^{\epsilon_0^{\epsilon_0}},\cdots) . But the second case seems more natural as we going by ordinals onwards, and limit of the sequence \epsilon_0,\epsilon_0*2,\epsilon_0*3,\cdots) is not \omega^{\epsilon+1} , but rather just \epsilon_0*\omega . We get that binary phi function is defined for all cases, and now the fast-growing hierarchy is formally defined up to \Gamma_0 (limit of binary phi function). This translates to BEAN and BAN as limit of expandal and backslash arrays respectively. Linear phi function Phi function can be extended for multiple arguments, allowing us to reach small Veblen ordinal. We still must deal only with two arguments, all others will be zeros. However, since we deal with multi-argument function, we must reduce the arity of it. Thus, one additional rule must be added. I shall use canonical # for the unchanged remainder and 0,...,0 for the string of zeroes (there can be 0 zeroes). The complete set of rules is given below: Rule P1. Condition: arity = 1 \phi(\alpha) = \omega^\alpha Repeat the block of rules A1-A3. Rule P2. Condition: first entry = 0 and arity > 1 \phi(0,\#) = \phi(\#) Rule P3. Condition: arity = 2, \alpha=1, \beta=S \phi(1,\beta+1)1 = \phi(1,\beta) \phi(1,\beta+1)n = \phi(1,\beta)^{\phi(1,\beta+1)n-1} Rule P4. Condition: \alpha=L,\beta=0 \phi(\#,\alpha,0,\cdots,0,0)n = \phi(\#,\alphan,0,\cdots,0,0) Rule P5. Condition: \alpha=L,\beta=S \phi(\#,\alpha,0,\cdots,0,\beta+1)n = \phi(\#,\alphan,\phi(\#,\alpha,0,\cdots,0,\beta)+1,\cdots,0,0) Rule P6. Condition: \alpha=S,\beta=0 \phi(\#,\alpha+1,0,\cdots,0,0)1 = \phi(\#,\alpha,0,\cdots,0,0) \phi(\#,\alpha+1,0,\cdots,0,0)n = \phi(\#,\alpha,\phi(\#,\alpha+1,0,\cdots,0,0)n-1,\cdots,0,0) Rule P7. Condition: \alpha=S,\beta=S , Rule P3 doesn't apply. \phi(\#,\alpha+1,0,\cdots,0,\beta+1)1 = \phi(\#,\alpha+1,0,\cdots,0,\beta)+1 \phi(\#,\alpha+1,0,\cdots,0,\beta+1)n = \phi(\#,\alpha,\phi(\#,\alpha+1,0,\cdots,0,\beta+1)n-1,\cdots,0,0) Rule P8. Condition: \beta=L \phi(\#,\alpha,0,\cdots,0,\beta)n = \phi(\#,\alpha,0,\cdots,0,\betan) This notation is equivalent to "linear array"-array notation in BEAF (with limit {X,X (1) 2}). Theta function up to LVO Instead of making multidimensional, tetrational, pentational, etc... variants of phi function (which are also possible), I can introduce theta function, defining it up to large Veblen ordinal in this part. Theta function without \Omega s is essentially just a binary phi function, so first 7 rules I shall keep the same. With \Omega s, it gets more powerful. Formally: Rule T1. Condition: \alpha=0 \theta(0,\beta)n = \omega^{\beta}n Rule T2. Condition: \alpha=1, \beta=S \theta(1,\beta+1)1 = \theta(1,\beta) \theta(1,\beta+1)n = \theta(1,\beta)^{\theta(1,\beta+1)n-1} Rule T3. Condition: \alpha=L, \beta=0 \theta(\alpha,0)n = \theta(\alphan,0) Rule T4. Condition: \alpha=L, \beta=S \theta(\alpha,\beta+1)n = \theta(\alphan,\theta(\alpha,\beta)+1) Rule T5. Condition: \alpha=S, \beta=0 \theta(\alpha+1,0)1 = \theta(\alpha,0) \theta(\alpha+1,0)n = \theta(\alpha,\theta(\alpha+1,0)n-1) Rule T6. Condition: \alpha=S,\alpha \geq 1, \beta=S \theta(\alpha+1,\beta+1)1 = \theta(\alpha+1,\beta)+1 \theta(\alpha+1,\beta+1)n = \theta(\alpha,\theta(\alpha+1,\beta+1)n-1) Rule T7. Condition: \beta=L \theta(\#,\beta)n = \theta(\#,\betan) Rule T8. Condition: \beta=0 \theta(\#+\Omega,0)1 = \theta(\#,0) \theta(\#+\Omega,0)n = \theta(\#+\theta(\#+\Omega,0)n-1,0) \theta(\#*\Omega,0)1 = \theta(\#,0) \theta(\#*\Omega,0)n = \theta(\#*\theta(\alpha*\Omega,0)n-1,0) Rule T9. Condition: \beta=S \theta(\#+\Omega,\beta+1)1 = \theta(\#+\Omega,\beta)+1 \theta(\#+\Omega,\beta+1)n = \theta(\#+\theta(\#+\Omega,\beta+1)n-1,0) \theta(\#*\Omega,\beta+1)1 = \theta(\#*\Omega,\beta)+1 \theta(\#*\Omega,\beta+1)n = \theta(\#*\theta(\#*\Omega,\beta+1)n-1,0) Rule T10. Condition: \alpha=L,\beta=0 \theta(\Omega^\alpha,0)n = \theta(\Omega^{\alphan},0) Rule T11. Condition: \alpha=L,\beta=S \theta(\Omega^\alpha,\beta+1)n = \theta(\Omega^{\alphan},\theta(\Omega^\alpha,\beta)+1) Since this notation can work with arbitrary countable \alpha and \beta , I can conclude that this notation indeed has limit at LVO. This is also limit of repeated usage of Bowers' "array of" operator. Theta function up to BHO If we allow \Omega to be added to be any level of power tower, we get to BHO. Let \Omega^{\cdots^{\Omega}} indicates any number of \Omega s down to 0, which closed under exponentiation. Then T3 and T4 will be removed, T8-T11 become T6-T9 and will be changed as follows: Rule T6. Condition: \beta=0 \theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},0)1 = \theta(\Omega^{\cdots^{\Omega^{\#}}},0) \theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},0)n = \theta(\Omega^{\cdots^{\Omega^{\#+\theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},0)n-1}}},0) \theta(\Omega^{\cdots^{\Omega^{\#*\Omega}}},0)1 = \theta(\Omega^{\cdots^{\Omega^{\#}}},0) \theta(\Omega^{\cdots^{\Omega^{\#*\Omega}}},0)n = \theta(\Omega^{\cdots^{\Omega^{\#*\theta(\Omega^{\cdots^{\Omega^{\#*\Omega}}},0)n-1}}},0) Rule T7. Condition: \beta=S \theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},\beta+1)1 = \theta(\Omega^{\cdots^{\Omega^{\#}}},\beta)+1 \theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},\beta+1)n = \theta(\Omega^{\cdots^{\Omega^{\#+\theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},\beta+1)n-1}}},0) \theta(\#*\Omega,\beta+1)1 = \theta(\#*\Omega,\beta)+1 \theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},\beta+1)n = \theta(\Omega^{\cdots^{\Omega^{\#+\theta(\Omega^{\cdots^{\Omega^{\#+\Omega}}},\beta+1)n-1}}},0) Rule T8. Condition: \alpha=L,\beta=0 \theta(\Omega^{\cdots^{\Omega^{\alpha}}},0)n = \theta(\Omega^{\cdots^{\Omega^{\alphan}}},0) Rule T9. Condition: \alpha=L,\beta=S \theta(\Omega^{\cdots^{\Omega^{\alpha}}},\beta+1)n = \theta(\Omega^{\cdots^{\Omega^{\alphan}}},\theta(\Omega^{\cdots^{\Omega^{\alpha}}},\beta)+1) I believe this is enough to reach the notation as powerful as {LX,1}n,n in BEAN, if it would be formally defined, and equivalent to Bird's Nested Hyper-Nested array notation. (Frozen until I shall learn more about higher uncontable ordinals.) Category:Blog posts